//
// Created by Administrator on 2023/11/15.
//
#include "iostream"
#include "queue"
#include "unordered_map"

using namespace std;
queue<string> q;
unordered_map<string, int> d;

void bfs(string state) {


    q.push(state);
    d[state] = 0;

    int dx[4]{-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    string end = "12345678x";
    while (!q.empty()) {
        string t = q.front();
        q.pop();

        if (t == end) {
            cout << d[t];
            return;
        }

        int now_d = d[t];

        //状态转移
        int pos = t.find('x');
        int x = pos / 3, y = pos % 3;
        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                swap(t[3 * a + b], t[pos]);
                if (!d.count(t)) //【交换完在进行判断】 如果当前状态未出现过，加入队列中，避免重复操作
                {
                    d[t] = now_d + 1; // 步数在之前的基础上+1
                    q.push(t); // 将当前状态加入队列
                }
                swap(t[3 * a + b], t[pos]);
            }
        }
    }
}

int main() {
    string state="23415x768";
    //cin >> state;
    bfs(state);

}